В настоящее время я пишу базовый синтаксический анализатор для XML. В качестве упражнения я реализую анализатор, управляемый таблицей LL. Это мой пример грамматики BNF: % строка данных имени токена %% / * LL (1) * / doc: elem elem: "<" open_tag open_tag: имя attr close_tag close_tag: ">" elem_or_data "" | "/>" ; elem_or_data: "<" open_tag elem_or_data | данные elem_or_data | / * эпсилон * / ; attr: name ":" строка attr | / * эпсилон * / ; Это правильная грамматика? Каждый терминальный литерал заключен в кавычки. Абстрактные терминалы обозначаются токеном%. Я кодирую рукописный лексер, чтобы преобразовать вводимые данные в список токенов. Как мне токенизировать абстрактные терминалы?
2021-03-03 08:12:13
Классический подход - написать регулярное выражение (или другой распознаватель) для каждого возможного терминала.
То, что вы называете «абстрактными» терминалами, которые совершенно конкретны, на самом деле являются терминалами, чьи связанные шаблоны распознают более одной возможной входной строки. Фактически распознанная строка (или некоторая вычисленная функция этой строки) должна быть передана синтаксическому анализатору как семантическое значение токена.
Номинально в каждой точке входной строки токенизатор запускает все распознаватели и выбирает тот, у которого больше всего совпадений. (Это так называемое правило «максимального пережевывания».) Обычно это можно оптимизировать, особенно если все шаблоны являются регулярными выражениями. (F) lex сделает эту оптимизацию, например, за вас.
Сложность в вашем случае заключается в том, что токенизация вашего языка зависит от контекста. В частности, когда целью является elem_or_data, единственными возможными токенами являются <, \ u003cpath fill-rule = \" evenodd \ "clip-rule = \" evenodd \ " = \ "M25.6622 17.6335C27.8049 17.6335 29.3739 16.9402 30.2537 15.6379C30.8468 14.7755 30.9615 13.5579 30.9615 11.9512V6.59049C30.9615 5.28821 30.4833 4.66231 29.4502 4.66233C28.4833 4.66231 29.4502 4.66231C28.41087C 4.58.4833 4.66231 29.4502 4.66233C28.410334.6554.69904.4502 4.66231C28.40334.6554.69904.405298.4089904.59603 4.65 .1369 4.56087 21.0134 6.57349 21.0134 9.27932C21.0134 11.9852 23.003 13.913 25.3754 13.913C26.5612 13.913 27.4607 13.4902 28.1109 12.6616C28.1109 12.7229 28.1161 12.7799 28.121 12.834.13011228425.2834.2832.128425.2834.28342 28.1161 12.7799 28.121 12.834.130112832234.27.28 15.2321 24.1352 14.9821 23.5661 14.7787C23.176 14.6393 22.8472 14.5218 22.5437 14.5218C21.7977 14.5218 21.2429 15.0123 21.2429 15.6887C21.2429 16.7375 22.9072 17.6335 25.6622 17.6317224.97.066 7327249249 7329249 7324249 7.63179 249 Z97.0 27.2119 7.09766 28.0918 7.94324 28.0918 9.27932C28.0918 10.6321 27.2311 11.5116 26.1024 11.5116C24.9737 11.5116 24.1317 10.6491 24.1317 9.27932Z \ "/ \ u003e \ u003cpath d = \" M16.809. 17845.29 13.45.28.95.1813.8962C19.3298 13.8962 19.8079 13.2535 19.8079 11.9512V8.12928C19.8079 5.82936 18.4879 4.62866 16.4027 4.62866C15.1594 4.62866 14.279 4.98375 13.3609 5.88013C12.653 5.05154 11.6581 4.62866 7286662 1332862 9.357329 4,67329 4,67329 4,67329 4,67329 4,67329 11.357329 11.357329 4,67 13.9157 13.2535 13.9157 11.9512V8.90741C 13.9157 7.58817 14.3365 6.91179 15.4269 6.91179C16.4027 6.91179 ед. .31675 5.28821 2.83866 4.66232 1.82471 4.66232C0.791758 4.66232 0.313354 5.28821 0.3131362354 6.5129049C 1,88 13,2535 3,316 75 11.9512V6. Z \ "fill = \" # 1BB76E \ "/> \ u003c / svg> \ u003c / a>",
contentPolicyHtml: "Вклады пользователей лицензированы на условиях \ u003ca href = \" https: //stackoverflow.com/help/licensing \ "\ u003ecc by-sa \ u003c / a> \ u003ca href = \" https://stackoverflow.com / legal / content-policy \ "> (политика содержания) \ u003c / a>",
allowUrls: true
},
onDemand: правда,
discardSelector: ".discard-answer"
, немедленноShowMarkdownHelp: true, enableTables: true, enableSnippets: true
});
}
});
Спасибо за ответ на Stack Overflow!
Обязательно ответьте на вопрос. Предоставьте подробную информацию и поделитесь своим исследованием!
Но избегайте…
Просить о помощи, разъяснениях или отвечать на другие ответы.
Делать заявления, основанные на мнении; Подкрепите их рекомендациями или личным опытом.
Чтобы узнать больше, ознакомьтесь с нашими советами по написанию отличных ответов.
Черновик сохранен
Черновик отклонен
Зарегистрируйтесь или войдите под своим ником
StackExchange.ready (функция () {
StackExchange.helpers.onClickDraftSave ('# ссылка для входа');
});
Зарегистрируйтесь с помощью Google
Зарегистрируйтесь через Facebook
Зарегистрируйтесь, используя электронную почту и пароль
Представлять на рассмотрение
Опубликовать как гость
Имя
Электронное письмо
Обязательно, но не отображается
StackExchange.ready (
function () {
StackExchange.openid.initPostLogin ('. New-post-login', 'https% 3a% 2f% 2fstackoverflow.com% 2fquestions% 2f54745855% 2ftokenize-abstract-terminal-in-ll-grammar% 23new-answer', 'question_page' );
}
);
Опубликовать как гость
Имя
Электронное письмо
Обязательно, но не отображается
Разместите свой ответ
Отказаться
Нажимая «Опубликовать ответ», вы соглашаетесь с нашими условиями обслуживания, политикой конфиденциальности и политикой использования файлов cookie.
Не тот ответ, который вы ищете? Посмотрите другие вопросы с метками parsing lexer bnf ll recursive-descent или задайте свой вопрос.